package graph;

/**
 * 前缀树
 *
 * @author Liaorun
 */
public class TrieTree {


    /**
     * 前缀树的节点，最多26个子分支
     */
    public static class TrieNode {
        public int pass;
        public int end;

        public TrieNode[] nexts;

        public TrieNode() {
            pass = 0;
            end = 0;
            // nexts[0] == null 没有走向‘a’的路
            // nexts[0] ！= null 有走向‘a’的路
            // ...
            // nexts[25] ！= null 有走向‘z’的路
            nexts = new TrieNode[26];
        }
    }

    /**
     * 根节点的pass代表加入了多少字符串，end代表加入了多少空串
     */
    public TrieNode root;

    public TrieTree() {
        this.root = new TrieNode();
    }

    /**
     * 在前缀树中添加一个字符串
     *
     * @param word 需要添加的字符串
     */
    public void insert(String word) {
        if (word == null) {
            return;
        }

        char[] chars = word.toCharArray();
        TrieNode node = root;
        node.pass++;
        int index;
        // 从左向右遍历字符
        for (char aChar : chars) {
            // 由字符，对应成走向那条路
            index = aChar - 'a';
            if (node.nexts[index] == null) {
                // 没有字符节点就创建一个
                node.nexts[index] = new TrieNode();
            }
            // 一个字符经过该节点一次
            node = node.nexts[index];
            // 记录++
            node.pass++;
        }
        // 一个字符串结束，终点节点end++
        node.end++;
    }


    /**
     * 获取一个字符串添加的次数
     *
     * @return 一个字符串添加的次数
     */
    public int getWordFrequency(String string) {
        if (string == null) {
            return 0;
        }

        char[] chars = string.toCharArray();
        TrieNode node = root;

        int index;

        for (char aChar : chars) {
            index = aChar - 'a';

            if (node.nexts[index] == null) {
                // 获取到的节点为空，表示一次都没有加过这个字符串
                return 0;
            }

            // 记录当前到达的节点
            node = node.nexts[index];
        }
        // 返回最后一个节点的end值，就为该字符串添加的次数
        return node.end;
    }


    /**
     * 加入的字符串中，有几个是以pre这个字符串作为前缀的
     *
     * @param pre 前缀字符串
     * @return 是以pre这个字符串作为前缀的字符串数量
     */
    public int prefixNumber(String pre) {
        if (pre == null) {
            return 0;
        }

        char[] chars = pre.toCharArray();

        TrieNode node = root;

        int index;
        for (char aChar : chars) {
            index = aChar - 'a';

            if (node.nexts[index] == null) {
                // 获取到的节点为空，表示一次都没有加过这个字符串
                return 0;
            }

            // 记录当前到达的节点
            node = node.nexts[index];
        }

        // 返回最后一个节点的pass值，就为以pre这个字符串作为前缀的字符串数量
        return node.pass;
    }

    public void delete(String word) {
        if (getWordFrequency(word) != 0) {
            // 存在才删除
            char[] chars = word.toCharArray();

            TrieNode node = root;
            node.pass--;
            int index;
            for (char aChar : chars) {
                index = aChar - 'a';
                // 每个对应字符的节点--pass,减去后等于 0，就将该节点删除，然后直接返回
                if (--node.nexts[index].pass == 0) {
                    node.nexts[index] = null;
                    return;
                }
                node = node.nexts[index];
            }
            // 最后一个节点的end--;
            node.end--;
        }
    }
}
